Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11003 - Boxes / 11003.2.cpp
blob19565f7c21c25ec6f1ee44a414a275566ca3d3b1
1 /*
2 Problem: 11003 - Boxes
3 From the UVa Online Judge
5 Author: Andrés Mejía-Posada
6 http://blogaritmo.factorcomun.org
8 Method: Dynamic programming
9 Complexity: O(n^2)
11 Accepted.
13 #include <iostream>
14 #include <algorithm>
16 using namespace std;
18 const int maxBoxes = 1000;
19 const int maxLoad = 3000;
20 int dp[maxBoxes][maxLoad+1];
22 dp[i][j] = maximum amount of boxes that can be stacked using boxes 0..i (included) such that I can still
23 add j more weight units on top.
26 int main(){
27 int n;
28 while (cin >> n && n){
29 for (int i=0; i<n; ++i)
30 for (int j=0; j<=maxLoad; ++j)
31 dp[i][j] = 0;
34 for (int i=0; i<n; ++i){
35 int w, l;
36 cin >> w >> l; //weight and load of box i-th
37 for (int j=0; j<= maxLoad; ++j){
38 if (j <= l) dp[i][j] = 1; //I can stack at least box i-th
39 //But maybe I can create a bigger stack with the same strength not using box i-th
40 if (i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j]);
42 if (j + w <= maxLoad && j <= l && i > 0){ //Now try to add box i-th on top of the previous boxes
43 dp[i][j] = max(dp[i][j], dp[i-1][j+w]+1);
47 cout << dp[n-1][0] << endl;
49 return 0;